package leetcode_81_100;

import utils.ListNode;

public class reverseBetween_92 {
    /**
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        /**
         * 想法是，用一个新链表从left倒序添加到right
         */
        if(left==right)return head;
        ListNode reverse=new ListNode(Integer.MAX_VALUE);
        ListNode front=head;
        ListNode root=head;
        int index = 1;
        while (root!= null) {
            if (index < left ) { //遍历前面部分的节点
                if (index < left - 1)   //后边是给front.next赋值，这里提前一步赋值
                    front = front.next;
            } else if (index > right) { //当遍历完需要反转的部分直接退出
                break;
            } else  {
                ListNode node = new ListNode(root.val);
                if (reverse.val != Integer.MAX_VALUE) //这里是为了去掉reverse尾部
                    node.next = reverse;  //倒序构建反转的链表
                reverse = node;
                if (index == right) //当构建完成
                    front.next = reverse;           //连接反转的部分
            }
            root = root.next;
            index++;
        }
        ListNode r = reverse;
        while (r.next != null){
            r = r.next;
        }
        r.next= root;       //连接尾部
        return left!=1?head:reverse; //当left==1直接返回reverse后边的即可
    }

    /**
     * 官解的简洁写法
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween2(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;  //永远指向待反转区域的第一个节点 left 的前一个节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;     //待反转区域的动态第一个节点 left
        ListNode next;                     //动态指向 curr 的下一个节点
        for (int i = 0; i < right - left; i++) {    // 1，2，3，4，5
            next = cur.next;  //3
            cur.next = next.next;    //cur指向下下个节点         2->4
            next.next = pre.next;   //next的下个节点指向首部节点，即left    3->2
            pre.next = next;  //把pre指向next，此时next变为left，从后边移到了最前     1->3
            // 1 -> 3 -> 2  -> 4  -> 5 此时3变为了left节点
        }
        return dummyNode.next;
    }

}
